package a_topologicalSort;

import java.util.Stack;

public class DFS {
	private final int max=10;
	private boolean[][] graph=new boolean[max][max];
	private int[] visit=new int[max];
	private int n;
	Stack<Integer> s;
	
	public DFS(){
		this.n=4;
		graph[1][2]=true;
		graph[4][2]=true;
		graph[2][3]=true;
		s=new Stack<>();
	}
	
	public static void main(String[] args){
		DFS s=new DFS();
		s.print();
	}
	
	public boolean dfs(int i){
		visit[i]=-1;//-1表示正在访问，0表示未访问，1表示已访问

		for(int j=1;j<=n;j++){
			if(graph[i][j]){
				if(visit[j]==-1)return false;
				else if(visit[j]==0&&!dfs(j))return false;
			}
		}
		visit[i]=1;
		s.push(i);
		return true;
	}
	
	public boolean topoSort(){
		for(int i=1; i <= n; i++)
		  {
		    if(visit[i]==0)
		    {
		      if(!dfs(i))// 如果存在环路则不能进行拓扑排序

		        return false;
		    }
		  }
		  return true;
	}
	
	public void print(){
		if(!topoSort())
		    System.out.println("has cycle!\n");
		  else{
		    while(!s.empty())
		    {
		    	System.out.println(s.peek());
		    	s.pop();
		    }
		  }
	}
}
